/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package cs;

import java.util.Scanner;

/**
 *
 * @author QuangHieu
 */
class TNode{
    int data;
    TNode left,right;
    TNode(int x){
        data=x;
        left=right=null;
    }
    TNode(int x, TNode l,TNode r){
        data=x;
        left=l;
        right=r;
    }
}

class MyTree {
    TNode root;
    MyTree(){
        root=null;
    }

    // duyet trung tu
    private void duyetTrungTu(TNode t){
        if(t!=null){
            duyetTrungTu(t.left);
            System.out.print(" "+t.data);
            duyetTrungTu(t.right);
        }
    }

    void duyetTrungTu(){
        duyetTrungTu(root);
    }

    //chieu cao cua cay
    private int chieuCao(TNode t){
        if(t==null)
            return 0;
        return 1+ Math.max(chieuCao(t.left),chieuCao(t.right));
    }

    int chieuCao(){
        return chieuCao(root);
    }

    //chen cho cay thanh cay can bang
    private TNode chenCanBang(TNode t, int x){
        if(t==null)
            return new TNode(x);
        if(chieuCao(t.left)>chieuCao(t.right))
            t.right=chenCanBang(t.right, x);
        else t.left=chenCanBang(t.left, x);
        return t;
    }

    void chenCanBang(int x){
        root=chenCanBang(root,x);
    }

    //tao cay
    private void taoCay(){
        root=null;
        int x;
        Scanner kb=new Scanner(System.in);
        while(true){
            System.out.print("\nNhap x de chen vao cay(nhap 0 de dung):");
            x=kb.nextInt();
            if(x==0)
                break;
            chenCanBang(x);
        }
    }

    //tim kiem
    private void tim(TNode t,int x){
        if(t==null){
            System.out.print("\nKhong");
            return ;
        }
        if(t.data==x){
            System.out.print("\nCo");
            return ;
        }
        tim(t.left,x);
        tim(t.right,x);
    }
    void tim(int x){
        tim(root,x);
    }

    //tim so lon nhat
    private int timMax(TNode t,int max){
        if(t==null) return max;
        if(t.data>max){
            max=t.data;
        }
        return Math.max(timMax(t.left,max),timMax(t.right,max));
    }

    int timMax(int max){
        return timMax(root,max);
    }

    // tinh trung binh cong
    private float trungBinh(TNode t){
        if(t==null)
            return 0;
        return t.data+trungBinh(t.left)+trungBinh(t.right);
    }

    private int soPhanTu(TNode t){
        if(t==null)
            return 0;
        return 1+soPhanTu(t.left)+soPhanTu(t.right);
    }
    float trungBinh(){
        
        return (float)trungBinh(root)/soPhanTu(root);
    }


    //dem so node co 1 con
    private int demSoNot1Con(TNode t){
        if(t==null)
            return 0;
        if((t.left==null&& t.right!=null) || (t.left!=null)&&(t.right)==null)
            return 1;
        return demSoNot1Con(t.left)+demSoNot1Con(t.right);
    }

    int demSoNot1Con(){
        return demSoNot1Con(root);
    }


    
    public static void main(String args[]){
        MyTree t=new MyTree();
        t.taoCay();
        System.out.print("Duyet trung tu: ");
        t.duyetTrungTu();
        //t.tim(5);
        System.out.print("\n"+t.timMax(-1));
        //System.out.print("\n"+t.trungBinh());
        System.out.print("\n"+t.demSoNot1Con());
        System.out.println();
    }
}
